package leetcode.code0321;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Stack;

public class Solution2bug extends Solution321 {

	@Override
	public int[] maxNumber(int[] nums1, int[] nums2, int k) {
		int len1 = nums1.length;
		int[][] n1 = this.sortNumIndex(nums1, len1);// 从大到小
		int len2 = nums2.length;
		int[][] n2 = this.sortNumIndex(nums2, len2);// 从大到小
		int[] ans = new int[k];
		Stack<int[]> s = new Stack<>();
		s.add(new int[] { 0, 0, 0, len1, len2 });
		while (!s.isEmpty()) {
			int[] params = s.pop();
			int cur = params[0]; // 当前处理是第几位
			int p1 = params[1]; // 当前指向nums1中第几个
			int p2 = params[2]; // 当前指向nums2中第几个
			int left1 = params[3];// 当前1中剩下几个
			int left2 = params[4];// 当前2中剩下几个
			for (int i = cur; i < k; i++) {
				// ????这块有问题, 比较大的问题 , 当前不行 不代表后续不行.
				int cleft1 = p1 == -1 ? 0 : len1 - n1[p1][1] - 1 + left2;// 如果选择1,后边还有几个数
				int cleft2 = p2 == -1 ? 0 : len2 - n2[p2][1] - 1 + left1;// 如果选择2,后边还要几个数
				int cleft = k - cur - 1;
				if (cleft1 < cleft && cleft2 < cleft) {
					break;// 选谁都不行
				}
				if (p1 != -1 && p2 != -1 && n1[p1][0] == n2[p2][0]) {// 两者一样,进栈
					ans[cur] = n1[p1][0];
					// 选p1进栈
					int temp1 = this.nextp(n1, p1);
					s.add(new int[] { cur + 1, temp1, p2, len1 - n1[temp1][1] + 1, left2 });
					// 选p2进栈
					int temp2 = this.nextp(n2, p2);
					s.add(new int[] { cur + 1, p1, temp2, left1, len2 - n2[temp2][1] + 1 });
					break;
				}
				if (p2 == -1 || cleft1 >= cleft && cleft2 < cleft) {
					// 必选1
					ans[cur++] = n1[p1][0];
					p1 = this.nextp(n1, p1);
					left1 = p1 == -1 ? 0 : len1 - n1[p1][1] + 1;
					continue;
				}

				if (p1 == -1 || cleft2 >= cleft && cleft1 < cleft) {
					// 必选2
					ans[cur++] = n2[p2][0];
					p2 = this.nextp(n2, p2);
					left2 = p2 == -1 ? 0 : len2 - n2[p2][1] + 1;
					continue;
				}

				if (n1[p1][0] > n2[p2][0]) {
					// 选p1
					ans[cur++] = n1[p1][0];
					p1 = this.nextp(n1, p1);
					left1 = p1 == -1 ? 0 : len1 - n1[p1][1] + 1;
				} else {
					// 选p2
					ans[cur++] = n2[p2][0];
					p2 = this.nextp(n2, p2);
					left2 = p2 == -1 ? 0 : len2 - n2[p2][1] + 1;
				}
			}
		}
		return ans;
	}

	private int nextp(int[][] n1, int cur) {
		int index = n1[cur][1];
		for (int i = cur + 1; i < n1.length; i++) {
			if (n1[i][1] > index) {
				return i;
			}
		}
		return -1;
	}

	private int[][] sortNumIndex(int[] nums, int len) {
		int[][] ans = new int[len][2];
		for (int i = 0; i < len; i++) {
			ans[i][0] = nums[i];
			ans[i][1] = i;
		}
		Arrays.sort(ans, (o1, o2) -> {
			if (o2[0] != o1[0])
				return o2[0] - o1[0];
			else
				return o1[1] - o2[1];
		});
		return ans;
	}

	private PriorityQueue<int[]> sort(int[] nums, int len) {
		PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> {
			if (o2[0] != o1[0])
				return o2[0] - o1[0];
			else
				return o1[1] - o2[1];
		});
		for (int i = 0; i < len; i++) {
			pq.add(new int[] { nums[i], i });
		}
		return pq;
	}

	public static void main(String[] args) {
		Solution2bug so = new Solution2bug();
//		so.debug1();
		so.debug2();
//		so.debug3();

	}

}
